Cool New Coin Problems
Alexander Gribalko designed a new coin problem, two versions of which appeared at the 43rd Tournament of the Towns. I will start with the easier version.
Problem. Alice and Bob found eleven identical-looking coins; four of them are fake. All real coins weigh the same. All fake coins weigh the same but are lighter than the real ones. Alice offered Bob four specific coins. Before agreeing to take them, Bob wants to ensure they are all real. Can he do so by only using the balance scale twice? He can use any of the eleven coins for weighing purposes.
Surprisingly, the more difficult version has fewer coins.
Share:Problem. Alice and Bob found eight identical-looking coins; three of them are fake. All real coins weigh the same. All fake coins weigh the same but are lighter than the real ones. Alice offered Bob three specific coins. Before agreeing to take them, Bob wants to ensure they are all real. Can he do so by only using the balance scale twice? He can use any of the eight coins for weighing purposes.
Sanandan Swaminathan:
Problem 1: Yes, using the two-pan balance scale at most twice, Bob can ascertain whether all 4 coins offered by Alice are real, or whether at least one of them is fake.
Let the 4 coins Alice offered be (A,B,C,D).
Weighing #1: Weigh (A,B) against (C,D). If this weighing is not balanced, then the 4 coins are not all identical, hence the 4 can’t all be real. So, Bob can reject the set (A,B,C,D) and he is done.
If weighing #1 is balanced, it means either (A,B,C,D) are all heavy, or all 4 coins are light, or weighing #1 had a heavy and a light coin on each pan. Do weighing #2: weigh (A,B,C,D) against any 4 coins from the other 7.
If all coins in (A,B,C,D) were light, then the other pan will necessarily show as heavier since it must be having 4 heavy coins.
Now consider the scenario where the (A,B,C,D) pan has 2 heavy coins and 2 light coins (resulting from a heavy and a light coin on each pan in weighing #1). If the other pan in weighing #2 has 4 heavy coins, or 3 heavies and 1 light, then the other pan will show as heavier. If the other pan has 2 heavies and 2 lights, weighing #2 will be balanced. If (A,B,C,D) has 2 heavies and 2 lights, then the other pan can’t have more than 2 lights.
However, if the (A,B,C,D) pan had all heavy coins, then the other pan can have at most 3 heavy coins. So, the pan containing (A,B,C,D) would show as heavier, and this is the only scenario in weighing #2 in which the pan containing (A,B,C,D) will show as heavier. So, in weighing #2, if (A,B,C,D) shows as heavier than the 4 coins on the other pan, then (A,B,C,D) contains all real coins. Otherwise, not all coins in (A,B,C,D) are real.
Problem 2: Yes, using the two-pan balance scale at most twice, Bob can ascertain whether all 3 coins offered by Alice are real, or whether at least one of them is fake.
Let the 3 coins Alice offered be A,B,C. Let the other 5 coins be D,E,F,G,H.
Weighing #1: Weigh (A,B,C) against (D,E,F). If (A,B,C) are all real (heavy), then the pan containing (A,B,C) will necessarily show as heavier (since the other pan could have at most 2 heavy coins in this scenario). So, if the pan containing (A,B,C) does not show as heavier (i.e. it shows as lighter, or weighing #1 is balanced), then (A,B,C) are not all real, hence Bob can reject (A,B,C) and he is done.
On the other hand, if weighing #1 shows the pan containing (A,B,C) as heavier, then…
28 June 2022, 8:50 pmEither
1) (A,B,C) contains 2 heavies and 1 light. In this case, (D,E,F) necessarily contains 1 heavy and 2 lights (since (D,E,F) couldn’t contain 3 lights when (A,B,C) contains 1 light). Also, coins G and H are both heavy in this scenario.
OR
2) (A,B,C) are all heavy (real).
To check whether he has hit case (1) or (2), Bob can do weighing #2: weigh (A,B,C) against (D,G,H).
If case (1) has been encountered, then (D,G,H) either contains 3 heavies (i.e. D was also a heavy coin apart from G and H) and the (D,G,H) pan would show as heavier, or (D,G,H) contains 2 heavies (G and H, with D being light) and weighing #2 would be balanced.
On the other hand, if case (2) has been encountered, the (A,B,C) pan will show as heavier in weighing #2 since (D,G,H) can have at most 2 heavies when (A,B,C) has 3 heavies. So, in weighing #2, if (A,B,C) shows as heavier than (D,G,H), then (A,B,C) contains all real/heavy. Otherwise, not all coins in (A,B,C) are real.
Sanjay Godse:
First Weighing.
Compare the specified four coins (SFC) with any four of the balance coins.
If SFC are all 4 real coins they will be always heavier as the other pan can have maximum 3 real coins.
If SFC have 3 real and 1 fake coins the balance can have any of the three possible positions.
If SFC have 2 or more fake coins, they cannot be heavier as the other pan can have 2 or less fake coins.
After first weighing if the SFC are lighter or balancing, the SFC contain at least one fake coin and discard the SFC.
If the SFC are heavier, go for second weighing.
Second Weighing.
2 July 2022, 4:28 amNow there are four coins either all are real or one of them is fake.
Make two groups of two coins each and compare. If they balance all 4 coins are real, else discard the SFC.
Sanjay Godse:
Another method for the first problem.
Let the specified four coins (SFC) be shown as (HHHH), (HHHL), etc.
First Weighing.
Let’s keep one coin side aside and compare SFC plus 1 coin with balance 5 coins.
A. If the kept aside coin is H the possible weighing positions are as follows.
(HHHH)H heavier than HLLLL
(HHHH)L heavier than HHLLL
(HHHL)H heavier than HHLLL
(HHHL)L equal to HHHLL
(HHLL)H equal to HHHLL
(HHLL)L lighter than HHHHL
(HLLL)H lighter than HHHHL
(HLLL)L lighter than HHHHH
(LLLL)H lighter than HHHHH
B. If the kept aside coin is L the possible weighing positions are as follows.
(HHHH)H is heavier than HHLLL
(HHHH)L is heavier than HHHLL
(HHHL)H is heavier than HHHLL
(HHHL)L is lighter than HHHHL
(HHLL)H is lighter than HHHHL
(HHLL)L is lighter than HHHHH.
(HLLL)H is lighter than HHHHH.
If the SFC containing pan is lighter than or balancing with the other pan, discard the SFC as it contains at least one fake coin.
Second Weighing.
Now we know that the SFC is either HHHH or HHHL.
From the SFC make two groups of two coins each and compare them with each other.
6 July 2022, 1:35 amIf they balance, all four coins (SFC) are real, else discard the SFC.
Sanjay Godse:
Another method for second problem.
Let the real coins be H ( heavier) and the fake coins be L (lighter).
Select any three coins (SC) and one coin from the balance five coins. We will show this fourth coin in brackets as (H) or (L).
The SC can be HHH or HHL or HLL or LLL.
First weighing.
Place 2 selected coins in the left pan and the 1 selected coin and the fourth coin in the right pan and compare.
The 15 possibilities are,
HH=H(H)
HH>H(L)
HH>L(H)
HH>L(L)
HL<H(H)
HL=H(L)
LHL(L)
LH=L(H)
LH>L(L)
LL<H(H)
LL<H(L)
LL<L(H)
If the left pan containing 2 of the SC is lighter, discard the SC as they contain at least one fake coin.
If the two pans balance, then in second weighing, compare the two coins from the right pan i.e. one selected coin and the fourth coin with each other. If they balance, the SC is all real coins, else discard the SC.
If the left pan containing two of the SC is heavier, then in second weighing, compare the two coins from the right pan i.e. one selected coin and the fourth coin with each other. If they balance then discard the SC. If they do not balance, and if the one selected coin is heavier than the fourth coin, the SC is all real ,else discard the SC.
25 July 2022, 5:57 amrosie:
Why do you consider Problem 2 harder? Sanandan Swaminathan’s solution to it seems to show that it is easier. Weigh A, B, C in the left pan first against D, E, F then against D, G, H in the right pan.
If A, B, C go down both times, all three are genuine. This is because, if any were fake, the right pan would have to have at least two fakes in each weighing. But with one fake among A, B, C there are at most two fakes in total in the right pan, so this isn’t possible. So A, B and C are all genuine.
There are only five genuine coins. So if A, B, C are all genuine, there must be at least one fake in the right pan in each weighing, so the left pan must go down both times. So if the left pan ever does not go down, A, B and C are not all genuine.
The two weighings are interchangeable, and we may even specify which coins to put in which pan in both weighings before doing the first weighing.
5 August 2022, 3:03 amtanyakh:
rosie, if I remember correctly the second was given to higher grades in the competition.
5 August 2022, 8:54 amwitzar:
Another method for the “easy” problem:
23 January 2023, 5:04 am(1) Show ABCDE > EFGHI. This proves ABCDE contains at most 1 light coin, as if it contained 2 or more, then EFGHI would have to contain 3 or more to be lighter, but there are only 4 light coins total.
(2) Show A < B. This proves that A is the only light coin within ABCDE, hence BCDE must be all heavy.